package 字符串.字符串排序;

import java.util.Arrays;

/**
 * @description:
 * @author: ywk
 * @date: 2021-08-24
 */
public class 高位优先的字符串排序 {
    public static void main(String[] args) {
        String[] sort = new String[]{"AEE0", "AB08", "AES0", "CEH8"};
        MSD.sort(sort);
        System.out.println(Arrays.asList(sort));

    }

    public static class MSD {
        private static int R = 256;
        private static final int M = 15;//小数组的切换阈值
        private static String[] aux;//数据费雷的辅助数组

        private static int charAt(String s, int d) {
            if (d < s.length()) {
                return s.charAt(d);
            }
            return -1;
        }

        public static void sort(String[] a) {
            int N = a.length;
            aux = new String[N];
            sort(a, 0, N - 1, 0);
        }

        private static void sort(String[] a, int lo, int hi, int d) {
            //以第d个字符为键将a[lo]到a[hi]排序
            if (hi <= lo + M) {
                insertSort(a, lo, hi, d);
                return;
            }
            int[] count = new int[R + 2];
            for (int i = lo; i <= hi; i++) {
                //计算频率
                count[charAt(a[i], d) + 2]++;
            }
            //将频率转化为索引
            for (int r = 0; r < R + 1; r++) {
                count[r + 1] += count[r];
            }
            //数据分类
            for (int i = lo; i <= hi; i++) {
                aux[count[charAt(a[i], d) + 1]++] = a[i];
            }
            for (int i = lo; i <= hi; i++) {
                a[i] = aux[i - lo];
            }
            //递归以每个字符为键排序
            for (int r = 0; r < R; r++) {
                sort(a, lo + count[r], lo + count[r + 1] - 1, d + 1);
            }
        }

        private static void insertSort(String[] a, int lo, int hi, int d) {
            for (int i = lo + 1; i <= hi; i++) {
                int start = i;
                while (start >= i && less(a[start],a[start - 1], d)){
                    start--;
                }
                swap(a, start, i);
            }
        }

        private static boolean less(String a, String b, int d) {
            return a.substring(d).compareTo(b.substring(d)) < 0;
        }

        public static void swap(String[] arr, int i, int j) {
            String temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
}
